package com.dyz.leetcode._05_sort;

import java.util.ArrayList;
import java.util.List;

public class _315_countSmaller {
    private int[] indexs;
    private int[] tmpIndexs;
    private int[] ans;
    public List<Integer> countSmaller(int[] nums) {
        //记录原始数组每个元素的索引信息，方便在合并的时候知道是计算哪个元素
        this.indexs = new int[nums.length];
        for(int i =0; i<nums.length; i++){
            indexs[i] = i;
        }
        this.tmpIndexs = new int[nums.length];
        this.ans = new int[nums.length];
        mergeSort(nums, 0, nums.length-1, new int[nums.length]);
        List<Integer> list = new ArrayList<Integer>();
        for (int num : ans) {
            list.add(num);
        }
        return list;
    }
    public void mergeSort(int[] nums, int lo, int hi, int[] tmp){
        if(lo>=hi){return;}
        //中间值
        int mid = lo + (hi-lo)/2;

        mergeSort(nums, lo, mid, tmp);
        mergeSort(nums, mid+1, hi, tmp);
        //合并
        merge(nums, lo, mid, hi, tmp);
    }

    public void merge(int[] nums, int lo, int mid, int hi, int[] tmp){
        for(int i=lo; i<=hi; i++){
            tmp[i] = nums[i];
            tmpIndexs[i] = indexs[i];
        }

        int i = lo;
        int j = mid+1;
        for(int k=lo; k<=hi; k++){
            if(i==mid+1){
                nums[k] = tmp[j];
                indexs[k] = tmpIndexs[j];
                j++;
            }else if(j==hi+1){
                nums[k] = tmp[i];
                indexs[k] = tmpIndexs[i];
                // 计算比当前元素小的后面元素的个数
                ans[tmpIndexs[i]] += j-mid-1;
                i++;
            }
            else if(tmp[i]<=tmp[j]){
                nums[k] = tmp[i];
                indexs[k] = tmpIndexs[i];
                // 计算比当前元素小的后面元素的个数
                ans[tmpIndexs[i]] += j-mid-1;
                i++;
            }else{
                nums[k] = tmp[j];
                indexs[k] = tmpIndexs[j];
                j++;
            }
        }
    }
}
